import collections
class Solution(object):
    def colorTheGrid(self, m, n):
        st = []
        space = []
        base = 10 ** 9 + 7
        def dfs(i):
            if i == m:
                space.append(tuple(st))
            else:
                if i == 0:
                    for j in range(3):
                        st.append(j)
                        dfs(i + 1)
                        st.pop()
                else:
                    for j in range(3):
                        if j != st[i - 1]:
                            st.append(j)
                            dfs(i + 1)
                            st.pop()
        dfs(0)
        d = {item: 1 for item in space}
        k = len(space)
        edges = collections.defaultdict(set)
        for i in range(k):
            for j in range(i + 1, k):
                c = 0
                for t in range(m):
                    if space[i][t] == space[j][t]:
                        c += 1
                if c == 0:
                    edges[space[i]].add(space[j])
                    edges[space[j]].add(space[i])
        for i in range(1, n):
            next_d = {item: 0 for item in space}
            for item in next_d:
                for last_item in edges[item]:
                    next_d[item] = (next_d[item] + d[last_item]) % base
            d = next_d
        return sum(d.values()) % base




data = Solution()
m = 5
n = 2
print(data.colorTheGrid(m, n))